给出 a,b,c 和 x1,x2,y1,y2, 问满足 ax+by+c=0 的 x1<=x<=x2 和 y1<=y<=y2 的对数有多少 (a,b,c,x1,x2,y1,y<=1018)
首先必须把a,b,c都处理0或正数
- 分类讨论a,b为0的情况
- 扩展欧几里得求出通解
- 算出合法的对数,x,y的k取交集
- 算区间左端点ceil,右端点floor,注意正数和负数取整不一样
Trick:想不通最后为什么a,b要除gcd(a,b)啊
我好难过.jpg
update:
考虑给ax+by=gcd(a,b)=d,ax项增加,bx减少,但和不变,这一项最小就是 lcm(a,b)
通解:
x=x0+k·b/gcd
y=y_0-k·a/\gcd(a,b)
1 |
|